我们正在构建什么 🎯
- 数据结构： 一个 优先队列（PQ）。
- 它是一种抽象数据类型，类似于列表或队列，但有其特殊之处。
- 每个元素都有一个“优先级”（即键值）。
- 当你执行“弹出”操作时，你总是始终获取优先级最高的元素。
- 操作：
- 1.
push(k) - 2.
peek() - 3.
pop()
- 1.
- 实现方式： 我们将使用一个 二叉最大堆。
- 为什么使用堆？ 它非常高效！堆能提供：
push: O(log N)pop: O(log N)peek: O(1)
什么是最大堆？
一种具有两个简单规则的二叉树：
1. 形状性质
它是一个 完全二叉树。所有层级都已填满，除了最底层可能未满，且最底层从左到右依次填充。不存在 空缺。
点击叶子节点以删除
2. 最大堆性质
父节点的键值 大于或等于 其子节点的键值。这保证了 最大 的元素始终位于根节点。
存储树结构 💾
因为该树是 完全的，我们可以将其完美地存储在一个简单的数组中。
索引计算（基于 0）
对于索引为 i 的节点：
- 父节点
(i - 1) // 2 - 左子节点
2 * i + 1 - 右子节点
2 * i + 2
提示： 记住这些公式！它们是你在数组中导航“树”的关键。